1. Field of the Invention
This invention generally relates to maximum a posteriori (MAP) decoders, and, more specifically, to efficiently performing decoding of large blocks of coded symbols or bits with a MAP decoder.
2. Background
MAP decoders were proposed over two decades ago in xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Rate,xe2x80x9d L. R. Bahl et al., IEEE Transactions on Information Theory, March 1974, pp. 27-30 (hereinafter referred to as xe2x80x9cthe Bahl referencexe2x80x9d). More recently, refinements to MAP decoders have been proposed in xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes,xe2x80x9d C. Berrou et al., Proc. ICC xe2x80x9993 Geneva, Switzerland, May 1993, pp. 1064-1070 (hereinafter referred to as xe2x80x9cthe Berrou referencexe2x80x9d). Both the Bahl and Berrou references are hereby fully incorporated by reference herein as though set forth in full.
Because of its increased complexity in relation to Viterbi decoders, the MAP decoder has not been widely adopted. The problem is compounded when long blocks are used, stemming from the use of long interleavers during the encoding process. To simplify the decoding process, a sliding window technique has been proposed in xe2x80x9cAn Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes,xe2x80x9d A. Viterbi, IEEE Journal On Selected Areas In Telecommunications, Vol. 16, No. 2, February 1998, pp. 260-264 (hereinafter referred to as xe2x80x9cthe Viterbi referencexe2x80x9d), which is hereby fully incorporated by reference herein as though set forth in full. However, the sliding window technique proposed in the Viterbi reference releases soft decisions in awkward fits and starts in which soft decisions for successive sub-blocks are released in consecutive order, but the soft decisions for each subblock are released in reverse order. Because of this order of data release, the sliding window technique proposed in the Viterbi reference is not efficient in the use of memory. Another problem is that there is a variable delay between the initiation of processing and the release of soft outputs. That makes subsequent processing utilizing the soft outputs more difficult.
In accordance with one aspect of the invention, there is provided a MAP decoding system in which one or more forward engines and one or more backward engines operate in unison to calculate the soft outputs for encoded symbols within a sliding window of a larger block. The one or more backward engines calculate backward probabilities over respective sub-blocks within a sliding window. In synchronization with the one or more backward engines, the one or more forward engines recursively calculate forward probabilities over the successive sub-blocks. In synchronization with the calculation of the forward probabilities, the one or more forward engines calculate and release soft outputs for the successive sub-blocks. The sliding window is then moved forward or backward and the calculations performed on a different portion of the block. The process repeats itself until the entire block has been processed.